Theory Discussion Group

From Theory Discussion Group

The Theory Discussion Group (TDG) is a student-run and student-led group of PhD students and postdocs interested in the general area of theoretical computer science. We meet weekly to present and discuss recent and classical results in CS theory of interest to the participants. We may also have some talks devoted to the research of the participants. Anybody with some interest in theory is welcome to attend. First-year students who want to look around in different areas and have some inclination towards theory are especially welcome. The discussion is typically more informal and comprehensive than the Monday theory seminar.

Schedule for Fall 2009

We will be meeting weekly on Fridays in 5126 at 1:15-2:15pm. You can sign up to present by editing an entry below. You can leave the topic and abstract blank at first, but please fill it in by about a week before you present.

September 18, 2009

• Speaker: Renato Paes Leme
• Topic: Competitive Auctions
• Abstract: This talk will cover the main material in a series of papers by Jason Hartline, Anna Karlin, Andrew Goldberg, Amos Fiat, ... about Competitive Auctions: the objective is to design an auction mechanism that achieves a certain profit compared to some benchmarks. We begin with a short introduction about Mechanism Design, the concept of truthfulness and the characterization of Truthful Mechanisms for Single Parameter Agents. Then we describe the Random Sampling Auction for Digital Goods and in the end we discuss open questions. An alternate source is those lecture notes by Jason Hartline.

September 25, 2009

• Speaker: Vasu Raman
• Topic: I'll be presenting the following STOC ’08 paper on games for exchanging, which proves negative results for “information exchanging problems” (think rational secret sharing) where player values are bounded, presenting protocols that work for unbounded player values that are finite in expectation. Those of you who took Eva’s course in the spring (6822), this is the paper Rachel presented, so you may want to skip if you still remember all the details.

Kol, G. and Naor, M. 2008. Games for exchanging information. In Proceedings of the 40th Annual ACM Symposium on theory of Computing (Victoria, British Columbia, Canada, May 17 - 20, 2008). STOC '08. ACM, New York, NY, 423-432.[1]

• Abstract: We deal with protocols that encourage participants to exchange information about their inputs for their mutual benefit. Our assumption is that the participants are rational and try to maximize their utility. Our goal is to design games and strategies where rational players do not have any incentive to deviate from the strategy.
  
  We investigate the problem of rational secret sharing, where a dealer pre-distributed shares of a secret which can in turn be reconstructed by the participants at a later stage. In addition, we consider the more general problem of rational function evaluation, where the participants wish to evaluate a given function of their values. We call the above problems 'information exchanging'.
  
  These tasks are two of the classical problems in foundations of cryptography, and have been intensively studied over the last three decades. However, their rational versions introduce new obstacles. One such obstacle is the behavior in the last round: if a participant knows that the current round is the last one, what is his incentive to send useful information?
  
  We show that schemes for the above tasks where player values come from a bounded (finite) domain cannot satisfy some of the most desirable properties of such protocols. For instance, for two parties no non-trivial exchange can have a Nash-equilibrium. In contrast, we suggest protocols for rational secret sharing where the values come from an unbounded domain, but with a finite (and polynomial sized) expectation. The protocol is a strict Nash equilibrium and it avoids the above mentioned problem of the last round.

October 2, 2009: NO SEMINAR (EaGL and Grace Hopper)

October 9, 2009: NO SEMINAR (Hopcroft Symposium)

October 16, 2009

• Speaker: Georgios Piliouras
• Topic: “Beyond Equilibria: Mechanisms for Repeated Combinatorial Auctions” by Brendan Lucier
• Abstract: We study the design of mechanisms in combinatorial auction domains. We focus on settings where the auction is repeated, motivated by auctions for licenses or advertising space. We consider models of agent behaviour in which they either apply common learning techniques to minimize the regret of their bidding strategies, or apply short-sighted best-response strategies. We ask: when can a black-box approximation algorithm for the base auction problem be converted into a mechanism that approximately preserves the original algorithm's approximation factor on average over many iterations? We present a general reduction for a broad class of algorithms when agents minimize external regret. We also present a new mechanism for the combinatorial auction problem that attains an $O(\sqrt{m})$ approximation on average when agents apply best-response dynamics.

October 23, 2009

• Speaker: Hu Fu
• Topic: Proving Integrality Gaps without Knowing the Linear Program, by Sanjeev Arora, Bela Bollobas, Laszlo Lovasz, Iannis Tourlakis, published in Theory of Computing, 2006. (Conference version in FOCS02)
• Abstract: Proving integrality gaps for linear relaxations of NPoptimization problems is a difficult task and usually undertaken on a case-by-case basis. We initiate a more systematic approach. We prove an integrality gap of 2 - o(1) for three families of linear relaxaions for Vertex Cover, and our methods seem relevant to other problems as well.

Since the speaker is completely new to the topic, more discussion than usual is expected.

October 30, 2009

• Speaker: Everyone
• Topic: Open Problem Session: Come prepared with an open question to share.

November 6, 2009

• Speaker: Alon Altman
• Topic: Internal Implementation
• Abstract: We introduce a constrained mechanism design setting called internal implementation, in which the mechanism designer is explicitly modeled as a player in the game of interest. This distinguished player has the opportunity to modify the game before play. Specifically, the player is able to make reliable binding commitments of outcome-specific monetary transfers to the other players in the game. We characterize the power of internal implementation for certain interesting classes of games, and show that the impact of internal implementation on the utility of the players' and the social welfare is often counterintuitive; for example, the social welfare can be arbitrarily worse after an internal implementation.

November 13, 2009

• Speaker: Anna Blasiak
• Topic: “Codes, Games and Entropy” from the book The Probabilistic Method by Noga Alon and Joel Spencer
• Abstract: I will begin by presenting and proving Shannon’s theorem.  I will then spend the majority of the time talking about two games called the “Lair Game” and the “Tenure Game.”  The games give a cute way to look at the question of coding over a noisy channel.   I will show a probabilistic proof of winning strategies (good encoding schemes) and then show how to derandomize them.  If time permits, I will present a theorem about the entropy of random variables and show how it can be applied to prove results about the size of a certain family of graphs.

November 20, 2009: Moved to 12-1pm, relocated to Upson 5135

• Speaker: Katherine Lai
• Topic: "A Constant Factor Approximation Algorithm for Generalized Min-Sum Set Cover" by Nikhil Bansal, Anupam Gupta, Ravishankar Krishnaswamy, SODA 2010
• Abstract: In the min-sum set cover problem, we are given a universe of elements and a collection of subsets, with each set S having a covering requirement of K(S). The objective is to pick one elemnt at a time such that the average covering time of the sets is minimized, where the covering time for a set S is the first time at which K(S) elements from S have been selected. (Generalized min-sum set cover is the same as the multiple intents re-ranking problem which was discussed in the approximation algorithms reading group over the summer.) I will present a randomized 485-approximation algorithm for this problem; it is the first algorithm with an O(1) guarantee in the general case, though there exist 2- and 4-approximations for special cases of this problem. If there is time, I will open it up to discussion about how to get a more reasonable or useful constant.

November 27, 2009: NO SEMINAR (Thanksgiving)

December 4, 2009

• Speaker: Everyone
• Topic: Open Problem Session: Come prepared with an open question to share.